﻿#define _CRT_SECURE_NO_WARNINGS 1
//day26-01 牛客：小红的ABC，题号：2305522
//解法1：动态规划——区间dp（回文串问题）
//int main()
//{
//    string s;
//    cin >> s;
//    int n = s.size();
//    int ret = 110;
//    vector<vector<bool>> dp(n, vector<bool>(n));
//    for (int i = n - 1; i >= 0; i--)
//    {
//        for (int j = i; j < n; j++)
//        {
//            if (s[i] == s[j])
//                dp[i][j] = (i + 1 < j ? dp[i + 1][j - 1] : true);
//
//            if (dp[i][j] && j - i + 1 > 1)
//                ret = min(ret, j - i + 1);
//        }
//    }
//    cout << (ret == 110 ? -1 : ret);
//    return 0;
//}

//解法2：找规律
//string s;
//int main()
//{
//	cin >> s;
//	int ret = -1; // 有可能并没有回⽂串
//	int n = s.size();
//
//	for (int i = 0; i < n; i++)
//	{
//		if (i + 1 < n && s[i] == s[i + 1]) // 判断⻓度为 2 的⼦串
//		{
//			ret = 2;
//			break;
//		}
//		if (i + 2 < n && s[i] == s[i + 2]) // 判断⻓度为 3 的⼦串
//		{
//			ret = 3;
//		}
//	}
//
//	cout << ret << endl;
//
//	return 0;
//}


//day26-02 牛客：不相邻取数，题号：1832016
//解法：动态规划——线性dp
//const int N = 1e6 + 10;
//typedef long long LL;
//LL arr[N];
////f[i]表示从前i个数中挑选，第i个数选，最大和
////g[i]表示从前i个数中挑选，第i个数不选，最大和
//LL f[N], g[N];
//int n;
//
//int main()
//{
//    cin >> n;
//    for (int i = 1; i <= n; i++) cin >> arr[i];
//    for (int i = 1; i <= n; i++)
//    {
//        f[i] = g[i - 1] + arr[i];
//        g[i] = max(g[i - 1], f[i - 1]);
//    }
//    cout << max(f[n], g[n]) << endl;
//    return 0;
//}


//day26-03 牛客：空调遥控，题号：2222857
//解法1：二分查找
//const int N = 1e6 + 10;
//int arr[N];
//int n, p;
//int main()
//{
//    cin >> n >> p;
//    for (int i = 1; i <= n; i++) cin >> arr[i];
//    sort(arr + 1, arr + 1 + n);
//    int l = arr[1] + p, r = arr[n] - p;
//    int ret = 0;
//    for (int i = l; i <= r; i++)
//    {
//        int a, b;
//        int left = 1, right = n;
//        while (left < right)
//        {
//            int mid = left + (right - left) / 2;
//            if (arr[mid] - i >= -p) right = mid;
//            else left = mid + 1;
//        }
//        a = left;
//        left = 1, right = n;
//        while (left < right)
//        {
//            int mid = left + (right - left + 1) / 2;
//            if (arr[mid] - i <= p) left = mid;
//            else right = mid - 1;
//        }
//        b = left;
//        ret = max(ret, b - a + 1);
//    }
//    cout << ret;
//    return 0;
//}

//解法2：滑动窗口
//const int N = 1e6 + 10;
//int n, p;
//int arr[N];
//int main()
//{
//	cin >> n >> p;
//	for (int i = 0; i < n; i++) cin >> arr[i];
//	sort(arr, arr + n);
//	int ret = 0, left = 0, right = 0;
//	p *= 2;
//	while (right < n)
//	{
//		while (arr[right] - arr[left] > p)
//		{
//			left++;
//		}
//		ret = max(ret, right - left + 1);
//		right++;
//	}
//	cout << ret << endl;
//	return 0;
//}